package com.springboot.java.design.search;

import com.springboot.java.design.data_structure.LinkedNode;

/**
 * @Author: TongRui乀
 * @Date: 2020-09-01 17:53
 * @description： 链表查询 --
 *      1 给定一个链表
 *      2 要求删除倒数第N个节点
 *      3 要求只能遍历一遍链表
 *
 *      思路：  使用两个指针 第一个指针遍历到N+1位置 第二个指针从Head开始
 *              两个指针同步向后遍历 直到第一个指针指向链表尾部
 *              而此时第二个指针指向的就是倒数第N个节点
 *
 */
public class LastLinkedList {


    public static void main(String[] args) {

        LinkedNode last = new LinkedNode("", 5, null);
        LinkedNode node4 = new LinkedNode("", 4, last);
        LinkedNode node3 = new LinkedNode("", 3, node4);
        LinkedNode node2 = new LinkedNode("", 2, node3);
        LinkedNode node1 = new LinkedNode("", 1, node2);

        printLinkedList(node1);

        getByOrder(node1, 2);

        printLinkedList(node1);

    }

    private static LinkedNode getByOrder(LinkedNode head, int n){

        LinkedNode first = head;
        LinkedNode second = head;

        // 第一个指针 到 N+1位置
        for (int i = 1; i <= n + 1; i++) {
            first = first.getNext();
        }

        while (first != null){
            first = first.getNext();
            second = second.getNext();
        }

        // 此时 second 的 next 就是 倒数N
        // 删掉 N
        second.setNext(second.getNext().getNext());

        return head;
    }

    public static void printLinkedList(LinkedNode head){

        if(head == null){
            return;
        }

        LinkedNode next = head;

        do {
            System.out.print(next.getValue() + "   ");
            next = next.getNext();
        }
        while (next != null);

        System.out.println();
    }


}
